{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1c7d0c23",
   "metadata": {},
   "source": [
    "## 基数排序\n",
    "1. 将整数转换为二进制表达\n",
    "2. 通过比特位分割实现降低算法的时间复杂度\n",
    "3. 基于计数排序法的稳定性，在函数内部调用该方法不断地对比特位不同的分割部分进行排序和综合"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d1e8b836",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "def radix_counting_sort(A, values, bin_values):\n",
    "    \"\"\" A对应截取二进制段的对应值，values对应原数值，bin_values对应原数值的二进制形式 \"\"\"\n",
    "    k = 0\n",
    "    for element in A:\n",
    "        if isinstance(element, int) is False or element < 0:\n",
    "            raise Exception(\"Element has to be integer and no minus.\")\n",
    "        if element > k:\n",
    "            k = element\n",
    "    buffer_array = []\n",
    "    for i in range(0, k + 1):\n",
    "        buffer_array.append(0)\n",
    "    for element in A:\n",
    "        buffer_array[element] += 1\n",
    "    for i in range(1, len(buffer_array)):\n",
    "        buffer_array[i] = buffer_array[i - 1] + buffer_array[i]\n",
    "    sorted_array = []\n",
    "    sorted_array_values = []\n",
    "    sorted_array_bin_values = []\n",
    "\n",
    "    for i in range(0, len(A)):\n",
    "        sorted_array.append(0)\n",
    "        sorted_array_values.append(0)\n",
    "        sorted_array_bin_values.append(0)\n",
    "    A = A[::-1]\n",
    "    values = values[::-1]\n",
    "    bin_values = bin_values[::-1]\n",
    "    for element, value, bin_value in zip(A, values, bin_values):\n",
    "        position = buffer_array[element]\n",
    "        sorted_array[position - 1] = element\n",
    "        sorted_array_values[position - 1] = value\n",
    "        sorted_array_bin_values[position - 1] = bin_value\n",
    "        buffer_array[element] -= 1\n",
    "    return sorted_array, sorted_array_values, sorted_array_bin_values\n",
    "\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "def radix_sorted(A:List[int]):\n",
    "    b = 0\n",
    "    for element in A:\n",
    "        if element.bit_length() > b:\n",
    "            b = element.bit_length()\n",
    "    \"\"\" 将元素转换为二进制字符串，例如 A = [10, 9, 2, 1]，元素对应二进制[0b1010, 0b1001, 0b10, 0b01].\n",
    "    由于数值元素中比特位个数最多为4，因此需要将所有元素对应的二进制比特位扩展成4，也就是将元素的二进制形式转换为\n",
    "    [0b1010, 0b1001, 0b0010, 0b0001].\"\"\"\n",
    "    bin_A = []\n",
    "    for element in A:\n",
    "        bin_element = ''\n",
    "        le = b - element.bit_length()\n",
    "        while le > 0:\n",
    "            bin_element += '0'\n",
    "            le -= 1\n",
    "        bin_element += bin(element)[2:]\n",
    "        bin_A.append(bin_element)\n",
    "            \n",
    "    n = len(A)\n",
    "    r = int(math.log(n, 2))\n",
    "    if b <= math.log(n, 2):\n",
    "        r = b\n",
    "    count = math.ceil(b / r)\n",
    "    end = b\n",
    "    begin = 0\n",
    "    while count > 0:\n",
    "        begin = 0 if end - r < 0 else end - r\n",
    "        values_for_sort = []\n",
    "\n",
    "        for element in bin_A:\n",
    "            v = int(element[begin : end])\n",
    "            values_for_sort.append(v)\n",
    "        V, A, bin_A = radix_counting_sort(values_for_sort, A, bin_A)\n",
    "        count -= 1\n",
    "        end -= r\n",
    "    return A\n",
    "\n",
    "\n",
    "A = [10, 9, 2, 1]\n",
    "A = radix_sorted(A)\n",
    "print(A)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b5f658e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before radix sort : [28, 845, 608, 906, 922, 807, 677, 12, 249, 898, 628, 516, 470, 881, 766, 768, 835, 451, 580, 105]\n",
      "After radix sort : [12, 28, 105, 249, 451, 470, 516, 580, 608, 628, 677, 766, 768, 807, 835, 845, 881, 898, 906, 922]\n"
     ]
    }
   ],
   "source": [
    "## 生成数据验证算法正确性\n",
    "import random \n",
    "N = 20\n",
    "A = []\n",
    "for i in range(N):\n",
    "    A.append(random.randint(1, 1000))\n",
    "print(f\"Before radix sort : {A}\")\n",
    "\n",
    "A = radix_sorted(A)\n",
    "print(f\"After radix sort : {A}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
